package java_0303_heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于整形的最大堆的实现
 * 根节点从0开始编号
 * 若此时节点编号为k,左子树编号：2k+1,右子树编号：2k+2,父节点编号：(k-1)>>1
 */
public class MaxHeap {
    //使用JDK内部动态数组存储
    List<Integer> data;

    public MaxHeap() {
        this(10);
    }
    //初始化堆的大小
    public MaxHeap(int size) {
        data=new ArrayList<>(size);
    }
    public boolean isEmpty(){
        return data.size()==0;
    }
    //根据索引得到父节点索引
    private int parent(int k){
        return (k-1)>>1;
    }
    //根据索引得到左子树索引
    private int leftChild(int k){
        return (k<<1)+1;
    }
    //根据索引得到右子树索引
    private int rightChild(int k){
        return (k<<1)+2;
    }
    /**
     * 3.将任意数组堆化
     * 也是个构造方法
     */
    public MaxHeap(int[] arr) {
        data=new ArrayList<>(arr.length);//初始化
        //1.先将arr所有元素复制到data数组中
        //（注意不是堆的添加，只是把所有元素放到data数组中）
        for (int i:arr) {
            data.add(i);
        }
        //2.从最后一个非叶子节点（最后一个叶子节点的父节点）开始siftDown(下沉)
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }

    }
    /**
     * 2.2查看当前最大堆的最大值
     */
    public int peekMax(){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty,can not peek");
        }
        return data.get(0);
    }
    /**
     * 2.取出当前最大堆的最大值
     */
    public int extractMax(){
        //取值注意判空
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty,can not extract");
        }
        //最大值在堆顶，取出，最后return就行
        int max=data.get(0);
        //取出最大值后的操作（取出最大值后新的堆的合并情况）
        //1.数组末尾元素顶到堆顶：索引为0位置元素变为末尾元素值
        data.set(0,data.get(data.size()-1));
        //2.删除数组末尾元素
        data.remove(data.size()-1);
        //3.元素下沉操作
        siftDown(0);
        return max;
    }

    /**
     * 元素下沉操作
     * @param k
     */
    private void siftDown(int k) {
        //终止条件：1.到达叶子节点：2k+1>size；2.左右子树较大值<k索引对应节点值
        while(leftChild(k)< data.size()){
            //j为左子树索引
            int j=leftChild(k);
            //判断是否有右子树
            if(j+1<data.size()&&data.get(j+1)>data.get(j)){
                //此时存在右子树并且右子树值比左子树的值大
                //给j+1让他成为右子树的索引
                j=j+1;
            }
            //此时j是左右子树较大值的索引，和当前节点k比较
            if(data.get(k)<data.get(j)){
                swap(k,j);
                //更新k索引位置
                k=j;
            }else{
                //k索引对应的节点值>=左右节点的最大值，无需再下沉，下沉操作结束
                break;
            }
        }
    }

    /**
     * 1.向最大堆中添加一个元素val
     */
    public void add(int val){
        //1.尾部添加元素(List集合的默认方法就是尾插)
        data.add(val);
        //2.进行元素上浮操作。最后一个元素的索引:data.size()-1
        siftUp(data.size()-1);
    }

    /**
     * 元素上浮操作
     * @param k
     */
    private void siftUp(int k) {
        //索引为k的元素进行上浮
        //上浮中止条件:1.k为索引的节点到达根节点（根节点索引为0）；2.k索引对应的值<=父节点值
        //则循环迭代条件：还存在父节点(k>0)&&当前节点值>父节点值(data.get(k)>data.get(parent(k)))
        while(k>0&&data.get(k)>data.get(parent(k))){
            //交换当前节点与父节点的值
            swap(k,parent(k));
            //k继续向上攀登
            k=parent(k);
        }
    }
    /**
     * 交换两个索引位置的值
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        int temp=data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }
    @Override
    public String toString() {
        return data.toString();
    }
}
